package j2024.j202412;

public class j1220 {
    /**
     * 24. 两两交换链表中的节点
     * 给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。
     * 你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
     * @param head
     * @return
     */
    public ListNode swapPairs(ListNode head) {
        if(head==null || head.next==null) return head;
        ListNode tmp = swapPairs(head.next.next);
        ListNode newHead = head.next;
        head.next = tmp;
        newHead.next = head;
        return newHead;
    }

    /**
     *
     *76. 最小覆盖子串
     * 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。
     * 如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
     * @param s
     * @param t
     * @return
     */
    public String minWindow(String s, String t) {
        char[] str = s.toCharArray();
        char[] tr = t.toCharArray();
        int[] hs = new int[128];
        int[] ht = new int[128];
        int kind = 0;
        int minlen = Integer.MAX_VALUE;
        int begin = -1;
        for (int i = 0; i < tr.length; i++) {
            if(ht[tr[i]]==0){
                kind++;
            }
            ht[tr[i]]++;
        }
        for (int left = 0,right=0,count=0; right < s.length(); right++) {
            //进入子串中
            char in = str[right];
            hs[in]++;
            if(hs[in]==ht[in]){
                count++;
            }
            //统计结果,出子串
            while(count==kind){
                int len = right-left+1;
                if(len<minlen){
                    minlen = len;
                    begin = left;
                }
                char out = str[left++];
                if(hs[out]==ht[out]){
                    count--;
                }
                hs[out]--;
            }
        }
        if(begin==-1){
            return "";
        }else {
            return s.substring(begin,begin+minlen);
        }
    }





















}
